COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	ENUMERATION OF TREE SHAPED MOLECULES
C00003 00003	.<< pub macros, declarations >>
C00027 ENDMK
C⊗;
ENUMERATION OF TREE SHAPED MOLECULES
N.G. DE BRUIJN
IN J. COMB. THEORY (LOOK UP NUMBER)

.<< pub macros, declarations >>
.DEVICE XGP
.
.PAGE FRAME 53 HIGH 75 WIDE
.AREA TEXT LINES 4 TO 54 ;
.TITLE AREA HEADING LINES 1 TO 3 ;
.TITLE AREA FOOTING LINE 56 ;
.
.TURN ON "≡" FOR "α";
.
.FONT 1 "BDR25.FNT[DOC,LMM]";	FONT 2 "BDI25";
.FONT 3 "NGB25";		FONT 4 "FIX25Z.FNT[DOC,LMM]";
.FONT 5 "CTL25";		FONT 6 "GRK25";
.AT "β" ⊂ TURN ON "{", "\" FOR "%" }\1{TURN OFF⊃;
.AT "λ" ⊂ TURN ON "{", "\" FOR "%" }\2{TURN OFF⊃;
.AT "∞" ⊂ TURN ON "{", "\" FOR "%" }\3{TURN OFF⊃;
.
.AT "α" ⊂ TURN ON "{", "\" FOR "%" }\5{TURN OFF⊃;
.AT "∧" ⊂ TURN ON "{", "\" FOR "%" }\6{TURN OFF⊃;
.comment << special chars %=chi, ∃=big sigma, #=script F, ⊗=circle, ↔ eqiv>>;
.comment << also @ is fancy f, ∂ is script O , ∨ is little sigma >> ;
.<< MAKE THESE ALWAYS COME FROM FIX25Z ... SO CAN BE INCLUDED >>
.AT "∃"⊂TURN ON "{", "\" FOR "%"}\6≡S\*{TURN OFF⊃
.AT "%"⊂TURN ON "{", "\" FOR "%"}\4≡%\*{TURN OFF⊃
.AT "#"⊂TURN ON "{", "\" FOR "%"}\4≡#\*{TURN OFF⊃
.AT "⊗"⊂TURN ON "{", "\" FOR "%"}\4≡⊗\*{TURN OFF⊃
.AT "↔"⊂TURN ON "{", "\" FOR "%"}\4≡↔\*{TURN OFF⊃
.AT "@"⊂TURN ON "{", "\" FOR "%"}\4≡@\*{TURN OFF⊃
.AT "∂"⊂TURN ON "{", "\" FOR "%"}\4≡∂\*{TURN OFF⊃
.AT "π"⊂TURN ON "{", "\" FOR "%"}\6≡P\*{TURN OFF⊃
.AT "∨"⊂TURN ON "{", "\" FOR "%"}\6≡s\*{TURN OFF⊃
.<< footnote macros >>
.FOOTSEP←"------------------";
.COUNT REFERENCE INLINE PRINTING "↑1"
.AT "<<" LABEL ":" TEXT ">" ⊂
.LABEL: NEXT REFERENCE!;!;
.SEND FOOT ⊂
.PREFACE 1; SPREAD←1; INDENT 0,0; TURNON "{";
{REFERENCE! LABEL}TEXT
.TURNOFF
.BREAK ⊃ ⊃
.
.<<label macros >>
.MACRO HD (HEADING) ⊂
.BEGIN IF LINES<10 THEN SKIP TO COLUMN 1 ELSE SKIP 2; NOFILL;
∞HEADINGβ
.END; ONCE PREFACE 1;⊃
.
.MACRO TITL (TITLE) ⊂
.BEGIN IF LINES<10 THEN SKIP TO COLUMN 1 ELSE SKIP 2; CENTER;
∞TITLEβ
.END;⊃
.
.MACRO GRAF (HDNG) ⊂ BREAK
∞HDNG.β
.⊃
.
.MACRO I6 ⊂ INDENT 6,6,6; SPREAD←1; PREFACE 1; ⊃
.MACRO SPACE1 ⊂ SPREAD←1; PREFACE 2; BREAK; ⊃
.MACRO SPACE2 ⊂ SPREAD←2; PREFACE 3; BREAK; ⊃
.
.TURNON "↑↓[]&";
.<<  Title page >>
.BEGIN CENTER
ENUMERATION OF THE GRAPHS OF MOLECULES

Larry Masinter
Computer Science Department
Stanford University
Stanford, California

May, 1973
.END
.GROUP SKIP 5
.BEGIN INDENT 6,6,6
ABSTRACT. Previously, enumerations of the number of equialence classes of
graphs with a given partitions have been given<<PARTHA:
K. R. Parthasarathy, Enumeration of Graphs with a Given Partitions,
Proc. Royal Dutch Acad. (Indag. Math.)>↑,<<OTHER:
R. C. Read, The Enumeration of Locally Restricted Graphs, Journal
London Math. Soc. 34 (1959)>
These results are
extended to give enumerations for the number of equivalence classes of
connected multigraphs.
Connected multigraphs correspond directly with chemical molecules; thus
the enumeration can be applied to count the number of chemical isomers
constructable from a given set of atoms.
Bounds may be placed on the
multiplicity of each edge, corrsponding to restrictions on multiple bonds
in chemical structures.
.END
.
.EVERY FOOTING(,{PAGE},)
.
.SKIP TO COLUMN 1
.SPACE2;
.HD INTRODUCTION
A λmulti-graphβ of order αnβ is the set αN={1,...,n}β (called the
λnodesβ of the graph) together with a mapping αfβ from the set
αE(n)={{i,j}|1≤i<j≤n}β to the set of non-negative integers αI↑+β.
Those αeεEβ for which αf(e)≠0β are said to be λedgesβ of the graph;
the λmultiplicityβ of αeβ is αf(e)β. Also, if αe={i,j}β then node
αiβ is said to be connected to node αjβ with multiplicity
αf({i,j})β. Multigraphs may be restricted to those whose edges have
maximum multiplicity αkβ by restricting the range of αfβ to be the
set of integers α{0,1,...,k}β. A αkλ-multigraphβ is thus an element
of αk+1↑[E(n)]β.

The λdegreeβ of a node αnεNβ is αd(n)=∃↓[m≠n]f({n,m})β. The degree
is the total number of other nodes αnβ is connected to, with each
connection counted the appropriate multiplicity number of times.

The λdegree seqenceβ of a graph αfβ is defined to be the ordered
list αds(f)=(o↓1,o↓2,...)β, where αo↓1≤o↓2≤...≤o↓nβ, and
α|{j:o↓j=k}|=|{l:d(l)=k}|β. It is the sorted list of the degrees of
the nodes of αfβ.

Given a set αXβ, the λsymmetry groupβ on αXβ, or αS↓Xβ, is defined
to be the set of all automorphisms from αXβ onto αXβ.

Two graphs αfβ, αgβ of order αnβ are said to be λisomorphicβ if there
exists a permutation α≡αεS↓Nβ such that α∀i,jεN f({i,j})=g({≡α(i),≡α(j)})β.
This is written αf↔gβ.

.GRAF Lemma
αf↔g => ds(f) = ds(g).β

Given a set αFβ and an equivalence relation ↔ on αFβ, we define
the set of equivalence classes of αFβ under ↔, αFβ/↔, to be
α{{fεF:f↔g} | gεF}β.

.HD STATEMENT OF PROBLEM
Thus, the the problem is to find a generating function for the
number of equivalence classes of k-multigraphs with a given
degree sequence α(o↓0,o↓1,o↓2,...)β.

.GRAF Burnside lemma
Let αEβ be a set, αGβ a finite group with a mapping α%:G→S↓Eβ.

Let αBβ be a finite set, and α#=B↑Eβ.

Define the equivalence relation ↔ for αf,gε#β, such that αf↔gβ
if there exists α≡αεGβ such that αf=g⊗%(≡α)β.

Let αwβ be a mapping αw:#→@β, where @ is a field, such that
αf↔g => w(f)=w(g)β. We call αwβ the weight function.

For αFβ an equivalence class in #/↔, define αW(F)β to be αw(f)β for any αfεFβ.

Then
.BEGIN NOFILL

α∃↓[↓[Fε#/↔]]W(F) 

 = ↑[ 1 ]&↓[|G|]&--- ∃↓[≡αεG]∃↓[↓[f=f⊗%≡α]]w(f).β
.END
To apply the Bernside lemma to this problem,
it is necessary to devise a weight function such that two graphs with
the same degree sequence have the same weight and graphs with different
degree sequences have different weights. Further, to construct a generating
function for the number of graphs with given degree sequences, the degree
sequences should be reflected in the exponents of terms in the weight rather
than in the coefficient.

Thus, we define the weight function αw↓oβ on αk↑[E(n)]β into the set of real
polynomials in αu↓1,u↓2,...,u↓nβ by:

αw↓o(f)=π↓[↓[1≤i<j≤n]](u↓iu↓j)↑[f({i,j})]β

The exponent of αu↓iβ in αw↓o(f)β will be the degree of node αiβ
in the graph α(N,f)β.
Unfortunately, αds(f)=ds(g)β (or even αf↔gβ) does not imply αw↓o(f)=w↓o(g)β;
although αfβ and αgβ have the same degree sequence, the exponents may be permuted
among the αu↓iβ.
It is necessary to apply a symmetrizing operator ∂:

.GRAF Definition
For αwβ a function in αu↓1, u↓2, ... u↓n,β define
.BEGIN NOFILL

α∂(w)(u↓1,u↓2,...,u↓n)
    =↑[1 ]&↓[n!]&[--]∃↓[≡αεS↓N]w(u↓[≡α↓1],u↓[≡α↓2],...,u↓[≡α↓n])β

Note:
        1) ∂ is linear
	2) if αwβ is symmetric, then α∂w=wβ;
	   specifically, α∂∂w=∂wβ for any αwβ.

The weight function w can now be defined by:
	for αfεk↑E,  w(f)=∂w↓o(f)β.
.END
This weight function satisfies our requirements:
If the degree sequence of αfβ is αo↓1≤o↓2≤o↓3≤...o↓nβ, the weight of αfβ
will be:
.BEGIN NOFILL

		α∂u↓1↑[o1]u↓2↑[o2]...u↓n↑[on]β
.END
Then, using the definition of ↔ given earlier, with
the representation of the group αG=S↓Nβ by α%(G), where
α%:S↓N→S↓E by %(≡β){i,j}={≡β(i),≡β(j)}β
we obtain:
.BEGIN NOFILL

α∃↓[↓[fε#/↔]]w(f)
        =↓[n!]&↑[1 ]&[--]∃↓[≡αεS↓n]∃↓[f=f⊗%≡α]w(f)
	=↓[n!]&↑[1 ]&[--] ∂∃↓[≡αεS↓n]∃↓[f=f⊗%≡α]w↓o(f)β
.END
Consider α∃↓[f=f⊗%≡α]w↓o(f)β and the cycles of %≡α.
αf=f⊗%≡α <=> fβ is constant on each cycle of %≡α.
For a given ≡α, let αM↓[≡α]β be the number of cycles of %≡α; for
α1≤r≤M↓[≡α]β, let αC↓r&↑≡αβ be the set of edges (elements of αEβ) in
the r-th cycle of %≡α, and
.	begin nofill

αU↓r↑[≡α]=π↓[↓[{l,p}εC↓r]]u↓lu↓pβ

Then for αf=f⊗%≡αβ,

αw↓o(f)=π↓[i,j](u↓iu↓j)↑[f({i,j})]

     =π↓[1≤r≤M](U↓r&↑[≡α])↑[f(cycle r)]β
.	end
Since each αf=f⊗%≡αβ can be specified by its value on the cycles
of %≡α, there is a 1-1 correspondence between such αfβ and
α∨ε{0,1,...,k}↑Mβ, where αkβ is the maximum multiplicity (can be ≡∞),
by α∨(r)=f(cycle r).β
In particular,
.	begin nofill

  αV(≡α)=∃↓[↓[f=f⊗%≡α]]w↓o(f) 
        =∃↓[↓∨] π↓[↓[1≤r≤M≡α]] (U↓r↑[≡α])↑[(r)]
        =π↓[↓[1≤r≤M≡α]]↑[↑[1-(U↓r)↑k]]&↓[↓[1 - U↓r]]&[-------] 
      (or π↓[↓[1≤rM≡α]]↑[↑[  1  ]]&↓[↓[1-U↓r]]&[-------] if k=≡∞)β
.	end
Our generating function is now
.begin nofill
         α↓[n!]&↑[1 ]&[--]∂∃↓[≡αεS↓N]V(≡α).β
.end continue
We wish to group the summation by those permutations ≡α with cycle index
α≡λ↓1+2≡λ↓2+...+n≡λ↓n=nβ (α≡λ↓iβ is the number of αiβ-cycles of ≡α; note that
this is different from the number of various cycles of %≡α).
Let α≡α⊗(≡λ↓1,≡λ↓2,...,≡λ↓n)β be the permutation obtained by filling in
the integers α1,...,nβ into the slots in
.	begin nofill

  (.)(.)...(.)     (..)(..)(..)   ...   (.. ...)
   ----------   ----------       -----
   ≡λ↓1 1-cycles  ≡λ↓2 2-cycles ... ≡λ↓n n-cycles
.	end
For α∨εS↓N, ∨≡α⊗∨↑[-1]β has the same cycle structure as ≡α; further, there
are exactly
.BEGIN NOFILL

αY(≡λ↓1,≡λ↓2,...,≡λ↓n)=π↓[1≤k≤n] (k↑[↑[≡λ]k]≡λ↓k!)β 
.END CONTINUE
such permutations. Thus,
.BEGIN NOFILL

α∃↓[≡αεS↓N]V(≡α)
      =∃↓[≡λ↓1+...+≡λ↓n=n]↓[Y(λ)]&↑[  1  ]&[-----] ∃↓[↓[∨εS↓N]]V(∨⊗≡α↓[≡λ]⊗∨↑[-1])β
.END